#include <stdio.h>

namespace JIANZHI_OFFER
{
	bool IsPosterBinarySearchTree(int* pData, int length)
	{
		if (pData == NULL)
			return false;
		if (length == 1)
			return true;
		int* pLeft = NULL;
		int* pRight = NULL;
		int root = pData[length - 1];
		for (int i = 0; i < length - 1; ++i)
		{
			if (pData[i] < root)
				pLeft = pData + i;
			else
				pRight = pData + i;
			if (pLeft && pRight && pLeft > pRight)
				return false;
		}
		if (!pLeft || !pRight)
			return IsPosterBinarySearchTree(pData, length - 1);
		else
			return IsPosterBinarySearchTree(pData, pLeft - pData + 1)
					&& IsPosterBinarySearchTree(pLeft+1, pRight - pLeft);
	}

	void TestIsPosterBinarySearchTree()
	{
		int data[7] = {5,7,6,9,11,10,8};
		IsPosterBinarySearchTree(data, 3) ?
			printf("is poster binary search tree!\n") :
			printf("is not poster binary search tree!\n");
	}
}